package find_code.blockSearch;

//分块查找，块内无序，块间有序
public class BlockSearch {
    public static void main(String[] args) {
        int[] arr = {16,5,9,12,21,18,
                32,23,37,26,45,34,
                50,48,61,52,73,66};

        Block block1 = new Block(21,0,5);
        Block block2 = new Block(45,6,11);
        Block block3 = new Block(73,12,17);

        Block[] blocks = {block1,block2,block3};

        int number = 37;

        System.out.println(getIndex(arr, blocks, number));

    }

    //获得查找的数字的下标
    public static int getIndex(int[] arr,Block[] blocks,int number){
        int blockIndex = blockIndex(blocks,number);
        if(blockIndex == -1)
            return -1;
        int startIndex = blocks[blockIndex].getStartIndex();
        int endIndex = blocks[blockIndex].getEndIndex();
        for (int i = startIndex; i <= endIndex; i++) {
            if(number == arr[i]){
                return i;
            }
        }
        return -1;
    }

    //确认查找的数字可能的分块
    public static int blockIndex(Block[] blocks,int number){
        for (int i = 0; i < blocks.length; i++) {
            if(number < blocks[i].getMax()){
                return i;
            }
        }
        return -1;
    }
}
